/**
 * 
 */
package string.passed;

import java.util.Stack;

/**
 * @author xyyi
 *
 */
public class LongestValidParentheses {
	/**
	Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

	For "(()", the longest valid parentheses substring is "()", which has length = 2.

	Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
	 */
	public int longestValidParentheses(String s) {
		if (s == null || s.isEmpty()) {
			return 0;
		}

		int max = 0, left = 0;
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				stack.push(i);
			} else {
				if (stack.isEmpty()) {
					left = i + 1;
				} else {
					stack.pop();
					if (stack.isEmpty()) {
						max = Math.max(max, i - left + 1);
					} else {
						max = Math.max(max, i - stack.peek());
					}
				}
			}
		}

		return max;
	}

	/*
	 * http://shawnxublog.blogspot.com/2012/10/longest-valid-parentheses-given-string.html
	 * time O(n) spaceO(1)
	 */
	public int longestValidParentheses2scan(String s) {
		if (s == null || s.isEmpty()) {
			return 0;
		}
		int max = 0;
		int left = 0;
		int count = 0;
		for (int i = 0, size = s.length(); i < size; i++) {
			if (s.charAt(i) == '(') {
				left++;
				count++;
			} else if (s.charAt(i) == ')') {
				left--;
				count++;
			}
			if (left == 0 && count > max) {
				max = count;
			} else if (left < 0) {
				left = 0;
				count = 0;
			}
		}

		int right = 0;
		count = 0;
		for (int i = s.length() - 1; i >= 0; i--) {
			if (s.charAt(i) == ')') {
				right++;
				count++;
			} else if (s.charAt(i) == '(') {
				right--;
				count++;
			}

			if (right == 0 && count > max) {
				max = count;
			} else if (right < 0) {
				right = 0;
				count = 0;
			}
		}

		return max;
	}

	public int longestValidParenthesesDP(String s) {
		if (s == null || s.isEmpty()) {
			return 0;
		}
		int max = 0;
		int[] dp = new int[s.length() + 1];
		// dp[i] the size of valid str end at s[i - 1]

		for (int i = 1; i <= s.length(); i++) {
			if (s.charAt(i - 1) == ')') {
				int j = i - 1 - dp[i - 1];
				if (j >= 1 && s.charAt(j - 1) == '(') {
					dp[i] = 2 + dp[i - 1] + dp[j - 1];
					max = Math.max(max, dp[i]);
				}
			}
		}

		return max;
	}

	//	public int longestValidParentheses(String s) {
	//		int i = 0;
	//		int maxLen = 0;
	//		Stack<Integer> stack = new Stack<Integer>();
	//		int left = 0; //deal with invalid brackets that reset counter
	//		while (i < s.length()) {
	//			if (s.charAt(i) == '(') {
	//				stack.push(i);
	//			} else {
	//				if (stack.empty())
	//					left = i + 1; //here has a invalid )
	//				else {
	//					stack.pop();
	//					if (stack.empty()) {
	//						maxLen = Math.max(maxLen, i - left + 1); //after invalid ) some bracket index offset
	//					} else {
	//						maxLen = Math.max(maxLen, i - stack.peek()); //deal with yet to process ( here
	//					}
	//				}
	//			}
	//			i++;
	//		}
	//		return maxLen;
	//	}

	/**
	 * 
	 */
	public LongestValidParentheses() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LongestValidParentheses lvp = new LongestValidParentheses();
		String s = "()(())";
		int result = lvp.longestValidParentheses(s);
		System.out.println(result);

	}
}
